package Array.easy;

import java.util.*;

/**
 * 1. 问题描述
 *      给你一个整数数组arr，请你将数组中的每个元素替换为它们排序后的序号。
 *      序号代表了一个元素有多大。序号编号的规则如下：
 *      序号从 1 开始编号。
 *      一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
 *      每个数字的序号都应该尽可能地小。
 *
 * 2. 算法分析
 *      算法分析：
 *             1. 我们先将原来的数组进行复制 调用数组的copy方法进行复制得到一个新的数组
 *             2. 对新数组进行排序 调用Arrays中的sort方法
 *             首先明确我们的目的是求出每一个元素(重复的元素算一次)的在排序之后的数组中的索引
 *             所以此时我们选取hashmap，其中key为元素，value为该元素的索引下表，而由于key不允
 *             许重复，所以自动取出重复元素
 *
 *             arr = [40,10,20,30,20]   --->   [10,20,20,30,40]
 *             map = {(10,0),(20,1),(30,2),(40,3)}
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 数组序号转换 {
    public static void main(String[] args) {

        Hashtable<Character,Integer> map = new Hashtable<>();
    }

    public static int[] arrayRankTransform(int[] arr) {
        int len = arr.length;
        int[] copyed = new int[len];
        copyed = arr.clone(); // 复制一个新数组
        Arrays.sort(copyed); // 对新数组排序
        Map<Integer,Integer> map = new HashMap<>(); // 创建hashmap
        int[] ans = new int[len];
        int index = 1; // 记录ans的值
        for(int i = 0; i < len; i++) {
            if(i > 0 && copyed[i] != copyed[i-1]) {
                map.put(copyed[i],index);
                index++;
            } else if (i == 0) {
                map.put(copyed[i],index);
                index++;
            }
        }
        for(int i = 0; i < len; i++) {
            // 注意：由于ans中的第i个元素指的是原数组第i个元素在排序之后的数组中的索引
            // 所以此时我们需要arr[i],而不是copyed[i]（第二个是排序之后的）
            ans[i] = map.get(arr[i]);
        }
        return ans;
    }


}
